/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

/**
 * @param {Node} head
 * @return {Node}
 */
var copyRandomList = function (head) {
  if (!head) return null;

  // 第一步：复制每个节点并插入原节点之后
  let current = head;
  while (current) {
    const copy = new Node(current.val);
    copy.next = current.next;
    current.next = copy;
    current = copy.next;
  }

  // 第二步：设置复制节点的 random 指针
  current = head;
  while (current) {
    if (current.random) {
      current.next.random = current.random.next;
    }
    current = current.next.next;
  }

  // 第三步：拆分原链表和复制链表
  const dummy = new Node(0);
  let copyCurrent = dummy;
  current = head;

  while (current) {
    copyCurrent.next = current.next;
    current.next = current.next.next;
    copyCurrent = copyCurrent.next;
    current = current.next;
  }

  return dummy.next;
};

/* 
这段代码通过「三次遍历」实现了随机链表的深拷贝，核心思路是利用原链表的节点关系暂存复制节点，避免使用哈希表额外存储映射关系，空间复杂度优化到 O (1)。以下是分步解析：
1. 核心问题
随机链表的深拷贝难点在于：
新节点的 next 指针需要指向复制链表的节点（而非原链表）。
新节点的 random 指针需要指向复制链表中对应的新节点（而非原链表）。
2. 代码分步解析
第一步：复制节点并插入原节点之后
javascript
let current = head;
while (current) {
  const copy = new Node(current.val); // 创建当前节点的复制节点
  copy.next = current.next; // 复制节点的next指向原节点的next
  current.next = copy; // 原节点的next指向复制节点
  current = copy.next; // 移动到下一个原节点（跳过复制节点）
}
效果：
原链表：A → B → C
处理后：A → A' → B → B' → C → C'
（A' 表示 A 的复制节点）
第二步：设置复制节点的 random 指针
javascript
current = head;
while (current) {
  if (current.random) {
    // 原节点A的random指向X，则A'的random指向X'
    current.next.random = current.random.next; 
  }
  current = current.next.next; // 跳过复制节点，移动到下一个原节点
}
关键逻辑：
若原节点 A.random = X，则复制节点 A'.random 应指向 X 的复制节点 X'。
由于第一步已将 X' 插入 X 之后（即 X.next = X'），因此 A'.random = X.next。
第三步：拆分原链表和复制链表
javascript
const dummy = new Node(0); // 复制链表的虚拟头节点
let copyCurrent = dummy;
current = head;

while (current) {
  copyCurrent.next = current.next; // 复制节点加入新链表
  current.next = current.next.next; // 原节点跳过复制节点，恢复原链表
  copyCurrent = copyCurrent.next; // 移动复制链表指针
  current = current.next; // 移动原链表指针
}


效果：
原链表恢复：A → B → C
复制链表生成：A' → B' → C'
3. 最终返回
javascript
return dummy.next; // 复制链表的头节点（跳过虚拟头节点）

4. 优势总结
空间效率：无需哈希表存储原节点与复制节点的映射，空间复杂度 O (1)。
时间效率：三次遍历链表，时间复杂度 O (n)。
通过「插入 - 设置 - 拆分」三步，巧妙利用原链表的结构完成复制，是随机链表深拷贝的经典解法。
*/